/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName   : Leetcode017 
 * @author      : ganwei 
 * @date        : 2020年5月4日
 * @Description : Leetcode017 电话号码的字母组合
 */
public class Leetcode0017 {
    private String letterMap[] = {
            " ",    //0
            "",     //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };
    private ArrayList<String> result = new ArrayList<String>();
	/**
	 * -解题思路,回溯算法，用于罗列所有的可能情况
	 */
    public List<String> letterCombinations(String digits) {
    	if(digits == null || digits.length() == 0) {
    		return result;
    	}
    	
    	conbin(digits, 0, new StringBuilder().append(""), letterMap);
    	
    	return result;
    }
    
    public void conbin(String digits, int depth, StringBuilder  sb, String[] lm) {
    	if(depth == digits.length()) {
    		result.add(sb.toString());
    		return;
    	}
    	char temp = digits.charAt(depth);
    	
    	String charArr = lm[Integer.valueOf(temp)-48];
    	for(int i = 0; i < charArr.length(); i++) {
    		//做出选择
    		sb.append(charArr.charAt(i));
    		conbin(digits,depth+1,sb,lm);
    		
    		//撤销选择
    		sb.deleteCharAt(sb.length() - 1);
    		
    	}
    }
    
    public static void main(String[] args){
    	Leetcode0017 l017 = new Leetcode0017();
    	System.out.println(l017.letterCombinations("23"));
    }
}
